Grokking Microsoft Coding Interview
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Introduction
Who Should Take This Course?
Microsoft Easy Problems
Buddy Strings (easy)
Solution: Buddy Strings
Can Place Flowers (easy)
Solution: Can Place Flowers
Reverse a LinkedList (easy)
Solution: Reverse a LinkedList
Maximum Number of Balloons (easy)
Solution: Maximum Number of Balloons
Binary Tree Path Sum (easy)
Solution: Binary Tree Path Sum
Pair with Target Sum (easy)
Solution: Pair with Target Sum
Buy Two Chocolates (easy)
Solution: Buy Two Chocolates
Root Equals Sum of Children (easy)
Solution: Root Equals Sum of Children
Excel Sheet Column Title (easy)
Solution: Excel Sheet Column Title
Merge Strings Alternately (easy)
Solution: Merge Strings Alternately
Min Cost Climbing Stairs (easy)
Solution: Min Cost Climbing Stairs
Plus One (easy)
Solution: Plus One
Intersection of Two Arrays (easy)
Solution: Intersection of Two Arrays
Find the Index of the First Occurrence in a String (easy)
Solution: Find the Index of the First Occurrence in a String
Merge Two Sorted Lists (easy)
Solution: Merge Two Sorted Lists
Microsoft Medium Problems
Nth Digit (medium)
Solution: Nth Digit
Restore IP Addresses (medium)
Solution: Restore IP Addresses
Find Original Array From Doubled Array (medium)
Solution: Find Original Array From Doubled Array
Reverse Words in a String II (medium)
Solution: Reverse Words in a String II
Longest Arithmetic Subsequence (medium)
Solution: Longest Arithmetic Subsequence
Matchsticks to Square (medium)
Solution: Matchsticks to Square
Score of Parentheses (medium)
Solution: Score of Parentheses
Maximum Length of a Concatenated String with Unique Characters (medium)
Solution: Maximum Length of a Concatenated String with Unique Characters
Inorder Successor in BST (medium)
Solution: Inorder Successor in BST
Distribute Coins in Binary Tree (medium)
Solution: Distribute Coins in Binary Tree
Spiral Matrix (medium)
Solution: Spiral Matrix
Delete Node in a BST (medium)
Solution: Delete Node in a BST
Sum of Subarray Minimums (medium)
Solution: Sum of Subarray Minimums
Rotate Image (medium)
Solution: Rotate Image
Combinations (medium)
Solution: Combinations
Maximum Level Sum of a Binary Tree (medium)
Solution: Maximum Level Sum of a Binary Tree
Multiply Strings (medium)
Solution: Multiply Strings
Best Time to Buy and Sell Stock II (medium)
Solution: Best Time to Buy and Sell Stock II
Largest Palindromic Number (medium)
Solution: Largest Palindromic Number
Remove Duplicate Letters (medium)
Solution: Remove Duplicate Letters
Next Permutation (medium)
Solution: Next Permutation
132 Pattern (medium)
Solution: 132 Pattern
Valid Sudoku (medium)
Solution: Valid Sudoku
Number of Islands (medium)
Solution: Number of Islands
Buildings With an Ocean View (medium)
Solution: Buildings With an Ocean View
Regular Expression Matching (hard)
Solution: Regular Expression Matching
First Missing Positive (hard)
Solution: First Missing Positive
Largest Rectangle in Histogram (hard)
Solution: Largest Rectangle in Histogram
Sliding Window Maximum (hard)
Solution: Sliding Window Maximum
Count Unique Characters of All Substrings of a Given String (hard)
Solution: Count Unique Characters of All Substrings of a Given String
Word Ladder (hard)
Solution: Word Ladder
Word Ladder II (hard)
Solution: Word Ladder II
Number of Flowers in Full Bloom (hard)
Solution: Number of Flowers in Full Bloom
Median of Two Sorted Arrays (hard)
Solution: Median of Two Sorted Arrays
Longest Valid Parentheses (hard)
Solution: Longest Valid Parentheses
Solution: Matchsticks to Square

Problem Statement

You are given an integer array matchsticks, where matchsticks[i] represents the length of the ith matchstick. You need to make one square by using these all matchsticks. You are not allowed to break any matchstick, but you can link them together, and you can use each matchstick only once.

Return true, if you make one square using all given matchsticks. Otherwise, return false.

Examples

  • Example 1:

    • Input: [5,5,5,5]
    • Expected Output: true
    • Justification: The matchsticks can be arranged to form a square with each side being 5 units long, using all the matchsticks exactly once.
  • Example 2:

    • Input: [3,3,3,3,4]
    • Expected Output: false
    • Justification: Despite having four matchsticks of the same length, the additional matchstick of length 4 prevents forming a perfect square.
  • Example 3:

    • Input: [1,1,2,1,2,1]
    • Expected Output: true
    • Justification: These matchsticks can be arranged to form a square with each side being 2 units long (1+1 for two sides and 2 for the other two sides).

Solution

To solve this problem, we adopt a backtracking approach which systematically explores all combinations of matchstick assignments to the sides of the square. We believe this approach is effective because it allows us to explore all potential arrangements while enabling us to backtrack if a certain arrangement does not lead to a solution. This flexibility is crucial given the nature of the problem, where the solution requires a specific distribution of matchsticks that might not be immediately apparent.

The key to this approach is to avoid redundancy and unnecessary computations by checking the feasibility of a partial solution before proceeding further. This method ensures that we only pursue promising leads, significantly reducing the search space and making the problem manageable within reasonable computational limits.

Step-by-step Algorithm

  1. Calculate the Total Length:

    • Sum up the lengths of all the matchsticks. This total length must be divisible by 4 for a square to be possible, as all four sides of the square must have equal length.
  2. Check for Basic Validity:

    • If the total length of matchsticks is not divisible by 4, return false immediately, as it's not possible to form a square.
  3. Determine Side Length:

    • Divide the total length by 4 to find the target length for each side of the square.
  4. Sort Matchsticks:

    • Sort the matchsticks in descending order. Starting with the longest matchsticks helps in reaching a solution faster or failing early if a solution isn't possible.
  5. Initialize Sides Array:

    • Create an array of 4 integers, each initialized to 0, to represent the current length of each side of the square as the algorithm progresses.
  6. Backtrack to Build the Square:

    • Starting with the first matchstick, attempt to place each matchstick on each side of the square one by one.
    • For each matchstick:
      • Try adding it to each side (one side at a time).
      • If adding the matchstick to a side does not exceed the target side length, recursively attempt to place the next matchstick.
      • If a matchstick cannot be placed on any side without exceeding the target length, backtrack: remove the last matchstick placed and try the next option.
    • If all matchsticks are successfully placed such that all four sides are of equal length, return true.
    • If some matchsticks cannot be placed successfully after trying all options, return false.
  7. Success or Failure:

    • The algorithm returns true if a combination that forms a square is found, otherwise false.

Algorithm Walkthrough

Let's consider the input [1,1,2,1,2,1].

  1. Total Length Calculation:

    • First, calculate the total length of all matchsticks: 1 + 1 + 2 + 1 + 2 + 1 = 8.
  2. Check for Basic Validity:

    • Verify if the total length is divisible by 4: 8 % 4 == 0, which is true. Therefore, a square might be possible.
  3. Determine Side Length:

    • Calculate the target length for each side of the square: 8 / 4 = 2.
  4. Sort and Reverse Matchsticks:

    • Sort the matchsticks in ascending order: [1, 1, 1, 2, 2, 1], then reverse the array to start with the largest matchsticks for efficiency: [2, 2, 1, 1, 1, 1].
  5. Backtracking to Place Matchsticks:

  • First Matchstick (2):

    • Place the first matchstick (2) on the first side, making the sides array [2, 0, 0, 0].
    • Call the backtrack function recursively to attempt placing the next matchstick.
  • Second Matchstick (2) in the Backtrack Function:

    • The first iteration of the loop skips the first side because 2 + 2 > 2 (exceeds target).
    • In the second iteration of the loop, place the second matchstick (2) on the second side, updating the sides array to [2, 2, 0, 0].
    • Recursively call the backtrack function to attempt placing the next matchstick.
  • Third Matchstick (1):

    • For the third matchstick, the first side is full, and the second side is also full. The third iteration places the matchstick on the third side, [2, 2, 1, 0].
    • Recursively call the backtrack function.
  • Fourth Matchstick (1):

    • For the fourth matchstick, the first two sides are full, and the third side already has a matchstick but the sum of sides[i]+ matchsticks[i] is less than or equal to target(2). The fourth matchstick is placed on the third side, updating the sides array to [2, 2, 2, 0].
    • Recursively call the backtrack function.
  • Fifth Matchstick (1):

    • For the fifth matchstick, the first side, second side, and third is full. The fourth iteration places the matchstick on the fourth side, [2, 2, 2, 1].
    • Recursively call the backtrack function.
  • Sixth Matchstick (1):

    • Finally, the sixth matchstick is placed on the fourth side, completing all sides to the target length. The sides array is updated to [2, 2, 2, 2].
    • With all sides equal to the target length, the condition for forming a square is met.
  • Return True:

    • Since the algorithm successfully placed all matchsticks without any side exceeding the target length and all sides equal to the target length, it returns true.

Code

Java
Saved to Cloud

. . . .

Complexity Analysis

Time Complexity

  • Worst-case scenario: , where is the number of matchsticks. In the worst case, the algorithm tries to place each matchstick in each of the four possible sides, leading to a recursive call tree of depth with a branching factor of 4.
  • Sorting: for sorting the matchsticks in descending order, which is a preprocessing step.

The overall time complexity is dominated by the backtracking process, making it in the worst case.

Space Complexity

  • Recursive Call Stack: , where is the number of matchsticks. This is the maximum depth of the recursive call stack.
  • Additional Space: for storing the matchsticks and the sides array.

The overall space complexity is , considering both the space for the input and the recursive call stack.

Matchsticks to Square (medium)
Score of Parentheses (medium)
Mark as Completed

On this page

Problem Statement

Examples

Solution

Step-by-step Algorithm

Algorithm Walkthrough

Code

Complexity Analysis